package com.coding.basic.stack;

import java.util.Arrays;
import java.util.EmptyStackException;

/**
 * 用一个数组实现两个栈
 * 将数组的起始位置看作是第一个栈的栈底，将数组的尾部看作第二个栈的栈底，压栈时，栈顶指针分别向中间移动，直到两栈顶指针相遇，则扩容。
 *
 * @author liuxin
 */
public class TwoStackInOneArray {
    private Object[] data = new Object[10];

    private int size1 = 0;
    private int size2 = 0;

    public TwoStackInOneArray(int capacity) {
        if (capacity <= 0) {
            throw new RuntimeException("capacity must > 0!");
        }
        data = new Object[capacity];
    }

    /**
     * 向第一个栈中压入元素
     */
    public void push1(Object o) {
        ensureCapacity();

        data[size1++] = o;
    }

    /**
     * 从第一个栈中弹出元素
     */
    public Object pop1() {
        if (size1 == 0) {
            throw new EmptyStackException();
        }

        Object value = data[size1 - 1];
        data[size1-- - 1] = null;

        return value;
    }

    /**
     * 获取第一个栈的栈顶元素
     */
    public Object peek1() {
        if (size1 == 0) {
            throw new EmptyStackException();
        }

        return data[size1 - 1];
    }

    /**
     * 向第二个栈压入元素
     */
    public void push2(Object o) {
        ensureCapacity();

        data[data.length - ++size2] = o;
    }

    /**
     * 从第二个栈弹出元素
     */
    public Object pop2() {
        if (size2 == 0) {
            throw new EmptyStackException();
        }

        Object value = data[data.length - size2];
        data[data.length - size2--] = null;

        return value;
    }

    /**
     * 获取第二个栈的栈顶元素
     */
    public Object peek2() {
        if (size2 == 0) {
            throw new EmptyStackException();
        }

        return data[data.length - size2];
    }

    private void ensureCapacity() {
        if (size1 + size2 < data.length) {
            return;
        }

        Object[] newData = new Object[data.length * 2];
        System.arraycopy(data, 0, newData, 0, size1);
        System.arraycopy(data, data.length - size2, newData, newData.length - size2, size2);

        data = newData;
    }

    public Object[] stack1ToArray() {
        return Arrays.copyOf(data, size1);
    }

    public Object[] stack2ToArray() {
        Object[] array = new Object[size2];

        for (int i = 0; i < size2; i++) {
            array[i] = data[data.length - i - 1];
        }

        return array;
    }
}
